/** 分治排序 */
function partition(a, start, end) {
  let l = start;
  let r = end;
  const pivot = a[start];
  while(l <= r) {
    while(l <= r && a[l] < pivot) {
      l++;
    }
    while(l <= r && a[r] > pivot) {
      r--;
    }
    if (l <= r) {
      [a[l], a[r]] = [a[r], a[l]] // 交换位置
      l++;
      r--;
    }
  }
}
/**
 * 快速排序基础版
 * @description 有一定的问题：1.基准值的选取；2.已实现排序的区间
 * @author luyaxiang
 * @date 2021/09/14
 * @param {*} a 等待排序的数组
 * @param {*} start 排序的开始位置
 * @param {*} end 排序的结束位置
 * @return {*} 
 */
function quickSort(a, start, end) {
  if (start == end) return; // 区间长度是1
  let l = start, r = end;
  const pivot = a[Math.floor((start + end) / 2)]; // 基准值，基准值的选中可以实现大部分的情况
  while(l <= r) {
    while(l <= r && a[l] < pivot) {
      l++;
    }
    while(l <= r && a[r] > pivot) {
      r--;
    }
    if (l <= r) {
      [a[l], a[r]] = [a[r], a[l]] // 交换位置
      l++;
      r--;
    }
  }
  quickSort(a, start, r);
  quickSort(a, l, end)
}


/**
 * 单边递归
 * 时间上没有减少很多，但是栈减少了！
 * 缺点：可读性低
*/
function quickSort1(a, start, end) {
  if (start == end) return; // 区间长度是1
  while(start <= end) {
    let l = start, r = end;
    const pivot = a[(l + r) >> 1]; // 基准值，基准值的选中可以实现大部分的情况
    while(l <= r) {
      while(l <= r && a[l] < pivot) {
        l++;
      }
      while(l <= r && a[r] > pivot) {
        r--;
      }
      if (l <= r) {
        [a[l], a[r]] = [a[r], a[l]] // 交换位置
        l++; r--;
      }
    }
    // console.info(l, end)
    arguments.callee(a, l, end);
    end = r;
  }
}

// 利用插入排序
function insertionSort(a, l, r) {
  let index = l;
  for (var i = l + 1; i <= r; i++) { // 找到最小的值对应的下标
    if (a[i] < a[index]) {
      index = i;
    }
  }
  while(index > l) { // 把最小的值前移到第一位，也就是l的位置
    [a[index], a[index - 1]] = [a[index - 1], a[index]];
    index--;
  }
  // 执行常规的插入排序
  for(var i = l + 2; i <= r; i ++) {
    let j = i;
    while(a[j] < a[j - 1]) {
      [a[j], a[j - 1]] = [a[j - 1], a[j]];
      j--;
    }
  }
}



const arr = [5, 7, 4, 3, 8];
quickSort1(arr, 0, arr.length - 1);
console.info(arr)